Network packet processing, such as forwarding and measurement of packets, often involves the use of table lookups. High speed network applications require fast and deterministic lookup performance. For example, at 10 Gbps line speed where up to 30 million packets can arrive at a line port per second, table lookups for a packet need to be finished in just 32 ns. While Content Addressable Memory (CAM) techniques satisfy this requirement, such a brute force approach to the lookup function is associated with high power consumption and low density.
Bloom filters play an important role in supporting many applications. They are very efficient in terms of memory consumption, such that fast hardware implementation is possible with embedded memory. However, a Bloom filter alone can only support membership queries; that is, answer the question of whether an element is in a table or not. A Bloom filter is incapable of giving any extra information about the queried element. For many applications, such associated information needs to be retrieved for the member elements.